package lc;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class WordBreak2 {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        return wordBreakMemoize(s, dict, new HashMap<String, ArrayList<String>>());
    }


	ArrayList<String> wordBreakMemoize(String s, Set<String> dict, HashMap<String, ArrayList<String>> sols) {
		ArrayList<String> result = new ArrayList<>();
    	if (s == null || s.length() == 0)  {
    		return result;
    	}
    	
    	for (int i=1; i<=s.length(); i++) {
        	String head = s.substring(0, i);
        	if (dict.contains(head)) {
        		String rest = s.substring(i);
        		if (rest.length() == 0) {
        			result.add(head);
        		}
        		else {
        			ArrayList<String> subResults;
        			if (sols.containsKey(rest)) {
        				subResults = sols.get(rest);
        			}
        			else {
        				subResults = wordBreakMemoize(rest, dict, sols);
        				sols.put(rest, subResults);
        			}
					for (String string : subResults) {
						result.add(head+" "+string);
					}
				}
        	}
        }
    	
    	return result;
	}

    
    public static void main(String ...strings) {
    	WordBreak2 sol = new WordBreak2();
    	String s = "catsanddog";
    	LinkedHashSet<String> dict = new LinkedHashSet<>(Arrays.asList(new String [] {
    			"cat", "cats", "and", "sand", "dog"
    	}));
    	ArrayList<String> wordBreak = sol.wordBreak(s, dict);
    	System.out.println(wordBreak);

    	String s1 = "a";
    	LinkedHashSet<String> dict1 = new LinkedHashSet<>(Arrays.asList(new String [] {    			
    	}));
    	ArrayList<String> wordBreak1 = sol.wordBreak(s1, dict1);
    	System.out.println(wordBreak1);
    
    	String s2 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
    	List<String> list = Arrays.asList(new String [] {    			
    			"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"
    	});
//    	Collections.reverse(list);
		LinkedHashSet<String> dict2 = new LinkedHashSet<>(list);
    	ArrayList<String> wordBreak2 = sol.wordBreak(s2, dict2);
    	System.out.println(wordBreak2);
    }
}
